package 背包问题;

public class Solution
{
    public static void main(String[] args)
    {
        int[] w = {2, 1, 3, 2};
        int[] v = {12, 10, 20, 15};
        System.out.println(knapSack1(w, v, 5));
    }

    //求这个物品中一个最有价值的子集，使得在满足背包的容量的前提下，包内的总价值最大
    //n个体积为w1 w2 w3..价值为v1 v2 v3..的物品和容量为C的背包
    //放不放第i个物品
    //不放，总价值等于前一个
    //不放第i个物品，此时总价值为F(i−1,C)
    //放置第i个物品，此时总价值为vi+F(i−1,C−wi)
    //取max
    //递归的方法
    //动态规划的方法
    //01背包
    public static int knapSack(int[] w, int[] v, int C)
    {
        int size = w.length;
        if (size == 0)
        {
            return 0;
        }
        //前一个相当于前i个物品
        int[][] dp = new int[size][C + 1];//C代表容量，多了一个容量为0的情况
        //初始化第一行
        //仅考虑容量为C的背包放第0个物品的情况
        for (int i = 0; i <= C; i++)
        {
            dp[0][i] = w[0] <= i ? v[0] : 0;
        }
        //能放的下第0个物品的容量，都会先放下第0个物品
        //绘制表格，相当于维护一个表格
        //填充其他行和列
        for (int i = 1; i < size; i++)
        {
            for (int j = 0; j <= C; j++)
            {
                if (j < w[i])//放不下当前物品
                    dp[i][j] = dp[i - 1][j];
                else //可以放下当前物品
                    dp[i][j] = Math.max(dp[i - 1][j], v[i] + dp[i - 1][j - w[i]]);

            }
        }
        return dp[size - 1][C];
        //还有空间复杂度的更优化版本
    }

    public static int knapSack1(int[] w, int[] v, int C)
    {
        int size = w.length;
        if (size == 0)
        {
            return 0;
        }

        int[] dp = new int[C + 1];
        //初始化第一行
        //仅考虑容量为C的背包放第0个物品的情况
        for (int i = 0; i <= C; i++)
        {
            dp[i] = w[0] <= i ? v[0] : 0;
        }

        for (int i = 1; i < size; i++)
        {
            // 滚动数组，每次都刷新dp
            for (int j = C; j >= w[i]; j--)//从后往前遍历，01背包必须是逆向遍历，完全背包是顺序遍历，用的是本次的数据
            {
                dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
            }
        }
        return dp[C];
    }

    //完全背包，物品无限拿
    public static int totalBackPag(int[] w, int[] v, int C)
    {
        int size = w.length;
        if (size == 0)
            return 0;
        int[][] dp = new int[size][C + 1];
        for (int i = 0; i <= C; i++)
        {
            dp[0][i] = w[0] <= i ? v[0] : 0;
        }
        for (int i = 1; i < size; i++)
        {
            for (int j = w[i]; j <= C; j++)
            {
               if (j<w[i])
                   dp[i][j]=dp[i-1][j];
               else
                   dp[i][j]=Math.max(dp[i-1][j],v[i]+dp[i][j-w[i]]);
            }
        }
        return dp[size-1][C];
    }
    //空间优化
    public static int totalBackPag1(int[] w, int[] v, int C)
    {
        int size = w.length;
        if (size == 0)
            return 0;
        int[] dp = new int[C + 1];
        for (int i = 0; i <= C; i++)
        {
            dp[i] = w[0] <= i ? v[0] : 0;
        }
        for (int i = 1; i < size; i++)
        {
            for (int j = w[i]; j <= C; j++)
            {
                if (j >= w[i])
                    dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
            }
        }
        return dp[C];
    }


}
